	IOI. 10 (Suprafete). N dreptunghiuri de culori diferite se suprapun
succesiv pe o foaie alba de hrtie, de dimensiuni a,b. Dreptunghiurile se
aseaza paralel cu laturile hrtiei si cad n interiorul ei. Ca rezultat,
vaznd de sus, se obtin diferite figuri de diferite culori. Doua regiuni de
aceeasi culoare se considera ca facnd parte din aceeasi figura daca au cel
putin un punct comun.
Valorile a,b sunt numere naturale pare, mai mici sau egale cu 30. Se cere aria
fiecarei figuri.
  Sistemul de coordonate are originea n centrul hrtiei si axele paralele cu
laturile hrtiei.
Fiecare set de date are forma:
- prima linie contine valorile a,b,N separate ntre ele prin cte un blanc;
- urmatoarele N linii contin fiecare: coordonatele ntregi ale punctului din
stnga jos al dreptunghiului respectiv, urmate de coordonatele ntregi ale
punctului de pe hrtie unde va fi plasat coltul din dreapta sus al
dreptunghiului, urmat de culoarea acestuia, care este din domeniul [1,64].
Culoarea alba are numarul 1.
  Ordinea liniilor n fisierul de intrare corespunde ordinii de asezare a
dreptunghiurilor. Seturile diferite de date sunt separate ntre ele printr-o
linie goala.
   Se cere sa se scrie un program care:
 1) Citeste succesiv seturile de date din fisierul de intrare;
 2) Calculeaza aria fiecarei figuri colorate, inclusiv n alb;
 3) Scrie ntr-un fisier text de iesire culoarea si aria fecarei figuri, ca n
exemplul urmator, n ordinea crescatoare a culorilor. Solutiile pentru seturi
diferite de date sunt separate ntre ele printr-o linie goala.
Exemplu: Pentru fisierul de intrare:
20 12 5
-7 -5 -3 -1 4
-5 -3 5 3 2
-4 -2 -2 2 4
2 -2 3 -1 12
3 1 7 5 1

30 30 2
0 0 5 14 2
-10 -7 0 13 15
fisierul de iesire trebuie sa aiba forma:
1 172
2 47
4 12
4 8
12 1

1 630
2 70
15 200
=========================================
Solutia 1 (Mihai Stroe)

    Problema este simpla si, daca se observa cum se pot respecta conditiile
  ( nu putem defini tipul Sistem_de_Coordonate, dar putem lucra pe o matrice,
  tinind cont de faptul ca lungimea unui segment de pe o dreapta este data de
  diferenta intre coordonatele referitoare la dreapta ale capetelor si nu de
  diferenta+1, deci segmentul [5,7] are lungimea 2 si nu 3; la introducerea in
  matrice a unui dreptunghi, coordonatele celui de-al doilea virf sunt micso-
  rate cu 1 ). Pentru fiecare dreptunghi se completeaza in matrice punctele
  corespunzatoare cu culoarea respectiva. Dupa obtinerea matricii, se va afla
  aria fiecarei figuri; calculul este realizat de o functie recursiva, care
  sterge figura pentru a nu o parcurge de mai multe ori. Algoritmul Fill,
  folosit pentru aceasta problema, este cunoscut si de aceea problema devine
  usoara. Probleme de acest gen s-au dat la multe concursuri. Timpul de
  rezolvare este de aproximativ 30 de minute.

var a:array[-15..15,-15..15]of byte;
    i,j,k,l,m,n,x,y,x1,y1,x2,y2:integer;
    fi,fo:text;
    s:string;

function aria(i,j:integer):integer;
begin
  if a[i,j]<>l then begin aria:=0;exit;end;
  a[i,j]:=0;
  aria:=1+aria(i-1,j)+aria(i+1,j)+aria(i,j-1)+aria(i,j+1);
end;

procedure readdata;
begin
  fillchar(a,sizeof(a),0);
  readln(fi,x,y,n);
  x:=x div 2;
  y:=y div 2;
  for i:=-x to x-1 do
      for j:=-y to y-1 do
          a[i,j]:=1;
  for l:=1 to n do
      begin
        readln(fi,x1,y1,x2,y2,k);
        for i:=x1 to x2-1 do
            for j:=y1 to y2-1 do
                a[i,j]:=k;
      end;
  readln(fi);
end;

procedure solve;
begin
  for l:=1 to 64 do
      begin
        for i:=-x to x-1 do
            for j:=-y to y-1 do
                if a[i,j]=l then
                   begin
                     m:=aria(i,j);
                     writeln(fo,l,' ',m);
                   end;
      end;
  writeln(fo);
end;

begin
  write('Type input file name ');
  readln(s);
  assign(fi,s);
  write('Type output file name ');
  readln(s);
  assign(fo,s);
  reset(fi);
  rewrite(fo);
  while not eof(fi)do
    begin
      readdata;
      solve;
    end;
  close(fi);
  close(fo);
end.
------------------------------
Solutia 2 (Mihai Badoiu)
   Ioi10 este problema foarte simpla.

var
        fo:text;
        a,b:integer;
        v:array[-64..64,-64..64] of byte;
        cul:integer;

function arie(x,y:integer):integer;
var
        aa:integer;
begin
        if v[y,x]<>cul then
        begin
                arie:=0;
                exit;
                end;
        v[y,x]:=0;
        aa:=1;
        aa:=aa+arie(x-1,y);
        aa:=aa+arie(x+1,y);
        aa:=aa+arie(x,y-1);
        aa:=aa+arie(x,y+1);
        aa:=aa+arie(x-1,y-1);
        aa:=aa+arie(x-1,y+1);
        aa:=aa+arie(x+1,y-1);
        aa:=aa+arie(x+1,y+1);
        arie:=aa;
end;

procedure calcul;
var
        i,j:integer;
begin
        for cul:=1 to 64 do
                for i:=-a to a do
                        for j:=-b to b do
                        if v[j,i]=cul then
                                writeln(fo,cul,' ',arie(i,j));
        writeln(fo);
end;

procedure load;
var
        f:text;
        nume:string;
        n:integer;
        i,i1,i2,x1,x2,y1,y2,c:integer;
begin
        write('fis in  = ');
        readln(nume);
        assign(f,nume);
        reset(f);
        write('fis out = ');
        readln(nume);
        assign(fo,nume);
        rewrite(fo);
        while not seekeof(f) do
        begin
                readln(f,a,b,n);
                for i1:=-(a div 2)+1 to (a div 2) do
                        for i2:=-(b div 2)+1 to (b div 2) do
                                v[i2,i1]:=1;
                for i:=1 to n do
                begin
                        readln(f,x1,y1,x2,y2,c);
                        for i1:=x1+1 to x2 do
                                for i2:=y1+1 to y2 do
                                        v[i2,i1]:=c;
                        end;
                calcul;
                end;
        close(f);
        close(fo);
end;

begin
        load;
end.
-----------------------------------------
Solutia 3 (Peter Szolt)
  Nu stiu care din ,a' si ,b' este marimea de X si Y. In rezorvarea mea ,a' este
marimea X si ,b' marimea Y.
  Dreptunghiurile citite am scris intr-un tablou. Dupa citire, cu o procedura
recrusiva am cautat formele si ariile acestora.

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 65384,0,655360}

program IOI10;
const
  Rezultat='rezultat.out';
  Max=16;
var
 s,s2:string;
 f,g:text;
 t:array[-max..max,-max..max] of byte;
 a,b:shortint;
 n,x1,x2,y1,y2,sz:integer;
 szin:set of 1..64;
 i,j,k:shortint;

function rek(i,j:integer):word;
begin
  if (i<-b+1) or (i>b) or (j<-a+1) or (j>a) then rek:=0 else
  if t[i,j]<>k then rek:=0 else begin
    t[i,j]:=0;
    rek:=rek(i-1,j)+rek(i-1,j-1)+rek(i-1,j+1)+rek(i+1,j)+rek(i+1,j-1)+rek(i+1,j+1)+
    rek(i,j-1)+rek(i,j+1)+1;
  end;
end;

begin
  write('Fisierul de intrare:');
  readln(s);
  assign(f,s);
  assign(g,Rezultat);
  reset(f);
  rewrite(g);
  while not eof(f) do begin
    readln(f,a,b,n);
    fillchar(t,sizeof(t),1);
    szin:=[1];
    for i:=1 to n do begin
      readln(f,x1,y1,x2,y2,sz);
      szin:=szin+[sz];
      for j:=y1+1 to y2 do
        for k:=x1+1 to x2 do
          t[j,k]:=sz;
    end;
    readln(f,s);
    a:=a div 2;
    b:=b div 2;
    for k:=1 to 64 do if k in szin then
      for i:=-b+1 to b do
        for j:=-a+1 to a do if t[i,j]=k then writeln(g,k,' ',rek(i,j));
    writeln(g,s);
  end;
  close(f);
  close(g);
end.
------------------------------
Solutia 4 (Catalin Francu)
program Suprafete;
type IntegerMatrix=array[0..31,0..31] of Integer;
var P:IntegerMatrix;
    A,B:Integer;
    InName,OutName:String;

procedure InitMatrix;
var i,j:Integer;
begin
  for i:=0 to B+1 do
    for j:=0 to A+1 do
      P[i,j]:=0;
  for i:=1 to B do
    for j:=1 to A do
      P[i,j]:=1;
end;

procedure MakeMatrix;
var N,i,j,k,X,Y,Z,T,Color:Integer;
begin
  ReadLn(A,B,N);
  InitMatrix;
  for k:=1 to N do
    begin
      ReadLn(X,Y,Z,T,Color);
      for i:=X+(A div 2)+1 to Z+(A div 2) do
        for j:=Y+(B div 2)+1 to T+(B div 2) do
          P[j,i]:=Color;
    end;
  if not Eof then ReadLn;
end;

function Area(X,Y,Color:Integer):Integer;
begin
  if P[X,Y]<>Color
    then Area:=0
    else begin
           P[X,Y]:=0;
           Area:=1+Area(X-1,Y-1,Color)+Area(X,Y-1,Color)+Area(X+1,Y-1,Color)
                 +Area(X+1,Y,Color)+Area(X+1,Y+1,Color)+Area(X,Y+1,Color)
                 +Area(X-1,Y+1,Color)+Area(X-1,Y,Color);
         end;
end;

procedure CountAreas;
var i,j,Color:Integer;
begin
  for Color:=1 to 64 do
    for i:=1 to B do
      for j:=1 to A do
        if P[i,j]=Color
          then WriteLn(Color,' ',Area(i,j,Color));
end;

begin
  Write('Numele fisierului de intrare: ');ReadLn(InName);
  Write('Numele fisierului de iesire: ');ReadLn(OutName);
  Assign(Input,InName);Reset(Input);
  Assign(Output,OutName);Rewrite(Output);
  while not Eof do
    begin
      MakeMatrix;
      CountAreas;
      WriteLn;
    end;
  Close(Input);Close(Output);
end.
---------------------------------------------
Solutia mea:
Algoritm:
Algoritmul este iterativ i lucreaz[ dup[ urm[toarea idee:
- coloreaz[ foaia de hrtie prin suprapunerea culorilor n ordinea citirii dreptunghiurilor;
- caut[ o celul[ colorat[; cnd a depistat-o, o recoloreaz[ ntr-o culoare nou[ i ncepe colorarea
vecinilor din aceeai figur[. Atragem atenia aici asupra a dou[ situaii limit[:
i) este posibil s[ existe un dreptunghi suprapus care s[ aib[ culoarea hrtiei;
ii) dup[ recolorarea unei celule, se rencepe c[utarea vecinilor celulei anterioare 9altfel sunt cazuri
cnd se pierd vecini).
O formalizare a acestei descrieri este:
1. citeste a,b,N; se defineste tabloul tab[-a/2..a/2,-b/2..b/2]
2. se umple tot tabloul tab cu 1 (culoarea alba a hartiei);
3. pentru i:=1,N
   3.1. citeste linia i: x1(i),y1(i),x2(i),y2(i),c(i)

   3.2. pentru k:=x1(i),x2(i)
           pentru j:=y1(i),y2(i)
              tab(k,j):=c(i)
   3.3. x1(0):=-a/2;x2(0):=a/2;y1(0):=-b/2;y2(0):=b/2;c(0):=1
4. pentru i:=0,N
    4'. pentru j1:=x1(i),x2(i)
           pentru j2:=y1(i),y2(i)
             4.1. daca tab(j1,j2)=c(i) atunci
                4.1.1. tab(j1,j2):=65+c(i); arie:=1
                4.1.2. pentru k1:=x1(i),x2(i)
                          pentru k2:=y1(i),y2(i)
                       daca |tab(k1,k2)-vecin(tab(k1,k2)|=65 atunci
                         arie:=arie+1;
                         tab(k1,k2):=65+c(i);vecin(tab(k1,k2)):=65+c(i)
                         k1:=k1-1;k2:=k2-1
                4.1.3. scrie c(i),arie
5. Stop
vecin(tab(i,j)) determina toate celulele vecine pe orizontal[ sau verticala cu tab(i,j),
situate n intyeriorul foii de hrtie.
Program:
uses crt;
type legatura=^dreptunghi;
     dreptunghi=record
                x1,y1,x2,y2,culoare:integer;
                urm:legatura;
                end;

var curent1,start,curent:legatura;
    input:text;
    arie,fcurent,primaf,numar_figuri,a,b,n,i,v:integer;
    d:dreptunghi;
    f:array[1..100] of legatura;
    intersecteaza:boolean;

function value(d1,d2:dreptunghi):integer;
var result:integer;
begin
result:=0;
if (d1.x1<=d2.x2) and (d1.x1>=d2.x1) then inc(result);
if (d1.x2<=d2.x2) and (d1.x2>=d2.x1) then inc(result);
if (d1.y1<=d2.y2) and (d1.y1>=d2.y1) then inc(result);
if (d1.y2<=d2.y2) and (d1.y2>=d2.y1) then inc(result);
if result=1 then result:=0;
value:=result;
end;

function in_point(d:dreptunghi;x,y:integer):boolean;
begin
in_point:=((x>=d.x1) and (x<=d.x2) and (y>=d.y1) and (y<=d.y2));
end;

function in_point_x(d:dreptunghi;x:integer):boolean;
begin
in_point_x:=((x>=d.x1) and (x<=d.x2));
end;

function in_point_y(d:dreptunghi;y:integer):boolean;
begin
in_point_y:=((y>=d.y1) and (y<=d.y2));
end;

procedure put_rectangle(x1,y1,x2,y2,c:integer);
var d:legatura;
begin
new(d);
d^.x1:=x1;
d^.y1:=y1;
d^.x2:=x2;
d^.y2:=y2;
d^.urm:=start;
d^.culoare:=c;
start:=d;
end;

procedure imparte(d1,d2:dreptunghi;n:integer);
var c:integer;
begin
c:=d2.culoare;
if n<>0 then
   begin
   if in_point(d2,d1.x1,d1.y1)then
      begin
      put_rectangle(d2.x1,d1.y1,d1.x1,d2.y2,c);
      put_rectangle(d2.x1,d2.y1,d2.x2,d2.y1,c);
      if n=3 then if in_point_x(d2,d1.x2) then
put_rectangle(d1.x2,d1.y1,d2.x2,d2.y2,c)
                  else if in_point_y(d2,d1.y2) then
put_rectangle(d1.x1,d1.y2,d2.x2,d2.y2,c);
      if n=4 then
         begin
         put_rectangle(d1.x1,d1.y2,d2.x2,d2.y2,c);
         put_rectangle(d1.x2,d1.y1,d2.x2,d1.y2,c);
         end;
      end
   else if in_point(d2,d1.x1,d1.y2) then
           begin
           put_rectangle(d2.x1,d2.y1,d1.x1,d2.y2,c);
           put_rectangle(d2.x1,d1.y2,d2.x2,d2.y2,c);
           if n=3 then if in_point_x(d2,d1.x2) then
put_rectangle(d1.x2,d2.y1,d2.x2,d1.y2,c)
                       else if in_point_y(d2,d1.y1) then
put_rectangle(d1.x1,d2.y1,d2.x2,d1.y1,c);
           if n=4 then
              begin
              put_rectangle(d1.x1,d2.y1,d2.x2,d1.y1,c);
              put_rectangle(d1.x2,d1.y1,d2.x2,d1.y2,c);
              end;
           end
   else if in_point(d2,d1.x2,d1.y1) then
        begin
        put_rectangle(d2.x1,d2.y1,d2.x2,d1.y1,c);
        put_rectangle(d1.x2,d1.y1,d2.x2,d2.y2,c);
        if n=3 then if in_point_x(d2,d1.x1) then
put_rectangle(d2.x1,d1.y1,d1.x1,d2.y2,c)
                    else if in_point_y(d2,d1.y2) then
put_rectangle(d2.x1,d1.y2,d1.x2,d2.y2,c);
        if n=4 then
           begin
           put_rectangle(d2.x1,d1.y1,d1.x1,d2.y2,c);
           put_rectangle(d1.x1,d1.y2,d1.x2,d2.y2,c);
           end;
        end
   else if in_point(d2,d1.x2,d1.y2) then
        begin
        put_rectangle(d2.x1,d1.y2,d2.x2,d2.y2,c);
        put_rectangle(d1.x2,d2.y1,d2.x2,d1.y2,c);
        if n=3 then if in_point_x(d2,d1.x1) then
put_rectangle(d2.x1,d2.y1,d1.x1,d1.y2,c)
                    else if in_point_y(d2,d1.y1) then
put_rectangle(d2.x1,d2.y1,d1.x2,d1.y1,c);
        if n=4 then
           begin
           put_rectangle(d2.x1,d2.y1,d1.x2,d1.y1,c);
           put_rectangle(d2.x1,d1.y1,d1.x1,d1.y2,c);
           end;
        end;
   end;
end;

procedure sterge(l:legatura);
var c:legatura;
begin
c:=start;
while c^.urm<>l do c:=c^.urm;
l:=c^.urm^.urm;
dispose(c^.urm);
c^.urm:=l;
end;

begin
clrscr;
assign(input,'input.i10');
reset(input);
readln(input,a,b,n);
start:=nil;
for i:=1 to n do
    begin
    readln(input,d.x1,d.y1,d.x2,d.y2,d.culoare);
    { daca dreptunghiul pus intersecteaza vreun alt dreptunghi }
    curent:=start;
    while curent<>nil do
          begin
          v:=value(d,curent^);
          if v<>0 then
             begin
             { imparte in dreptunghirile vizibile }
             imparte(d,curent^,v);
             { si sterge dreptunghiul care a fost acoperit }
             sterge(curent);
             end;
          curent:=curent^.urm;
          end;
    { adauga dreptunghiul la lista }
    put_rectangle(d.x1,d.y1,d.x2,d.y2,d.culoare);
    end;
{ construieste figurile }
curent:=start;
numar_figuri:=0;
for i:=1 to 100 do f[i]:=nil;
while curent<>nil do
      begin
      { testeaza daca dreptunghiul curent intersecteaza vreo figura }
      fcurent:=1;
      primaf:=0;
      while f[fcurent]<>nil do
            begin
            { pentru toate dreptunghiurile din figura }
            curent1:=f[fcurent];
            intersecteaza:=false;
            while (curent1<>nil) and (not intersecteaza) do
                  begin
                  if (value(curent1^,curent^)<>0) and
(curent1^.culoare=curent^.culoare) then intersecteaza:=true
                  else curent1:=curent1^.urm;
                  end;
            { daca face parte din figura fcurent }
            if intersecteaza then
               begin
               { daca este prima figura intersectata }
               if primaf=0 then
                  begin
                  { adauga dreptunghiul la figura }
                  curent1:=f[fcurent];
                  new(f[fcurent]);
                  f[fcurent]^:=curent^;
                  f[fcurent]^.urm:=curent1;
                  primaf:=fcurent;
                  end
               else
                  begin
                  { daca nu este prima figura intersectata }
                  { adauga figura curenta la prima ficura intersectata }
                  curent1:=f[primaf];
                  while curent1^.urm<>nil do curent1:=curent1^.urm;
                  curent1^.urm:=f[fcurent];
                  f[fcurent]:=nil;
                  dec(numar_figuri);
                  end;
               end;
            inc(fcurent);
            end;
      if primaf=0 then
         begin
         { daca nu a intersectat nici o figura }
         { creeaza o noua figura care contine dreptunghiul curent }
         inc(numar_figuri);
         new(f[numar_figuri]);
         f[numar_figuri]^:=curent^;
         f[numar_figuri]^.urm:=nil;
         end;
      curent:=curent^.urm;
      end;
i:=1;
{ listeaza figurile }
while i<=numar_figuri do
    begin
    while (f[i]=nil) and (i<=numar_figuri) do inc(i);
    if f[i]<>nil then
       begin
       arie:=0;
       write(f[i]^.culoare,'  ');
       curent:=f[i];
       while curent<>nil do
             begin
             arie:=arie+(curent^.x2-curent^.x1)*(curent^.y2-curent^.y1);
             curent:=curent^.urm;
             end;
       writeln(arie);
       end;
    inc(i);
    end;
end.
--------------------------------------
